package com.LeetCode.Array.Sort;

import org.junit.Test;

/**
 * 摆动排序
 */
public class wiggleSort {

    int n = -1;

    public void wiggleSort(int[] nums) {
        //找到中位数索引
        int midIndex = this.quickSelect(nums,0,nums.length-1);
        //找到中位数
        int mid = nums[midIndex];
        n=nums.length;
        //三分法
        for(int i=0,j=0,k=nums.length-1;j<=k;){
            if(nums[V(j)]>mid){
                swap(nums,V(j++),V(i++));
            }else if(nums[V(j)]<mid){
                swap(nums,V(j),V(k--));
            }else{
                j++;
            }
        }
    }

    public int V(int i){
        return (1+2*(i)) % (n|1);
    }

    public void swap(int[] nums,int i,int j){
        int t = nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }

    public int quickSelect(int[] nums, int left, int right){
        int povit = nums[left];
        int l = left;
        int r = right;
        while(l<r){
            while(l<r && nums[r] >= povit){
                r--;
            }
            if(l<r)
                nums[l++] = nums[r];
            while(l<r && nums[l] <= povit){
                l++;
            }
            if(l<r){
                nums[r--] = nums[l];
            }
        }
        nums[l] = povit;
        if(l == nums.length/2)
            return l;
        else if(l > nums.length / 2)
            return quickSelect(nums, left, l - 1);
        else
            return quickSelect(nums, l + 1, right);
    }

    @Test
    public void test(){
        int[] arr = {1, 5, 1, 1, 6, 4};
        wiggleSort(arr);
        for(int num : arr){
            System.out.print(num + " ");
        }
    }

    @Test
    public void testInteger(){

        Integer a = 1;
        Integer b = 1;
        Integer c = 500;
        Integer d = 500;
        System.out.print(a == b);
        System.out.print(c == d);
    }

    @Test
    public void testString(){
        String str =
                "";
        System.out.print(str.split(",").length);
    }

}
